package com.xk._02算法篇._09bloomFilter;

/**
 * @description: 布隆过滤器
 * @author: xu
 * @date: 2022/10/20 22:30
 */
public class BloomFilter<T> {
    /**
     * 二进制向量的长度（一共有多少个二进制位）
     */
    private int bitSize;
    /**
     * 二进制向量
     */
    private long[] bits;
    /**
     * 哈希函数的个数
     */
    private int hashFuncSize;

    /**
     * @param n 数据规模
     * @param p 误判率 取值范围(0, 1)
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("wrong n or p");
        }
        double ln2 = Math.log(2);
        // 求出二进制向量的长度
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
        // 求出哈希函数的个数
        hashFuncSize = (int) (bitSize * ln2 / n);
        // bits数组的长度
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }

    /**
     * 添加元素
     * @return true代表bit发生了改变
     */
    public boolean put(T value){
        nullCheck(value);
        // 利用 value 生成 2 个整数
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;

        boolean isChanged = false;
        for (int i = 1; i <= hashFuncSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) combinedHash = ~combinedHash;
            // 生成一个二进制位的索引
            int index = combinedHash % bitSize;
            // 设置第index位置的二进制位为1
            if (set(index)) isChanged = true;
        }
        return isChanged;
    }

    /**
     * 判断一个元素是否存在
     * @param value
     * @return false代表一定不存在，true代表可能存在
     */
    public boolean contains(T value) {
        nullCheck(value);
        // 利用 value 生成 2 个整数
        int hash1 = value.hashCode();
        int hash2 = hash1 >>> 16;

        for (int i = 1; i <= hashFuncSize; i++) {
            int combinedHash = hash1 + (i * hash2);
            if (combinedHash < 0) combinedHash = ~combinedHash;
            // 生成一个二进制位的索引
            int index = combinedHash % bitSize;
            // 判断index位置的二进制位是否为1
            if (!get(index)) return false;
        }
        return true;
    }

    /**
     * 设置index位置的二进制位为1
     * @param index
     */
    private boolean set(int index) {
        int bitsIndex = index / Long.SIZE;
        int idx = index & (Long.SIZE - 1);
        // 找到对应的long
        long value = bits[bitsIndex];
        bits[bitsIndex] = value | (1 << idx);
        return (value & (1 << idx)) == 0;
    }

    /**
     * 判断index位置的二进制位是否为1
     * @param index
     */
    private boolean get(int index) {
        int bitsIndex = index / Long.SIZE;
        int idx = index & (Long.SIZE - 1);
        // 找到对应的long
        long value = bits[bitsIndex];
        return (value & (1 << idx)) != 0;
    }

    private void nullCheck(T value){
        if (value == null) {
            throw new IllegalArgumentException("Value must not be null");
        }
    }
}
